package com.ztom.dp;

/**
 * 最大子数组和
 * <p>
 * https://leetcode-cn.com/problems/maximum-subarray/
 *
 * @author ZhangTao
 */
public class Code10MaxSubArray {

    public int maxSubArray2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] max = {nums[0]};
        process(nums, nums.length - 1, max);
        return max[0];
    }

    private int process(int[] nums, int i, int[] max) {
        if (i == 0) {
            return nums[0];
        }
        int preMax = process(nums, i - 1, max);
        int curMax = Math.max(nums[i], preMax + nums[i]);
        max[0] = Math.max(max[0], curMax);
        return Math.max(nums[i], preMax + nums[i]);
    }

    public int maxSubArray1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = nums[0];
        int preMax = 0;
        for (int num : nums) {
            preMax = Math.max(num, preMax + num);
            max = Math.max(max, preMax);
        }
        return max;
    }
}
